package org.kfive.nova.algorithm.sort;

/**
 * Created with IntelliJ IDEA.
 * User: admin
 * Date: 14-5-13
 * Time: 上午9:53
 * To change this template use File | Settings | File Templates.
 */
public class MegerSort {

    public static void meger(int [] source,int start1,int end1,int start2,int end2){
        int i=start1;
        int j=start2;
        int n=0;
        int [] temp = new int [end2-start1+1];
        while (i<=end1&&j<=end2){
            if(source[i]<source[j]){
                temp[n++]=source[i++];
            }else {
                temp[n++]=source[j++];
            }
        }
        while (i<=end1){
            temp[n++]=source[i++];
        }
        while (j<=end2){
            temp[n++]=source[j++];
        }
        n=start1;
        for(int element:temp){
            source[n++]=element;
        }
    }

    public  static void megerSort(int []source,int start,int end){
        if(start<end){
            int mid = (start+end)/2;
            megerSort(source, start,mid);
            megerSort(source, mid+1, end);
            meger(source,start,mid,mid+1,end);
        }
    }


    public static void main(String [] args){
        int [] source = {8,3,6,8,1,2,0,4,1,56,78,123,45,98};
        megerSort(source,0,source.length-1);
        for (int i=0;i<source.length;i++){
            System.out.println(source[i]);
        }
    }
}
